package alg.tree;

/**
 * @author:yuziji
 * @create: 2023-04-20 18:48
 * @description:二叉树的最近公共祖先
 * 所有节点的值都是唯一的。
 * p、q 为不同节点且均存在于给定的二叉树中。
 */
public class LowestCommonAncestor {

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);
        root.right.right = new Node(7);

        Node n = lowestCommonAncestor(root,root.left.left,root.right.left);
        System.out.println(n.value);
    }

    private static Node lowestCommonAncestor(Node root, Node p, Node q) {
        if (root == null){
            return null;
        }
        if (root == p || root ==q){
            return root;
        }
        Node left = lowestCommonAncestor(root.left, p, q);
        Node right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null){
            return root;
        }
        if (left!=null){
            return left;
        }
        if (right != null){
            return right;
        }

        return null;
    }

    static class Node{
        int value;
        Node left;
        Node right;

        Node(int value){
            this.value = value;
        }
    }
}
